#include <bits/stdc++.h>
// 2025/01/19
// tag: 
// Author: Zhang Muen
using namespace std;
class State
{
public:
    int id, weight;
    State(int i, int w)
    {
        id = i;
        weight = w;
    }
};

struct cmp
{
    bool operator()(State &a, State &b)
    {
        return a.weight > b.weight;
    }
};

int n, m, s, dist[100001];
unordered_map<int, int> graph[100001];

void Dijkstra(int start)
{
    for (int i = 1; i <= n; i++)
        dist[i] = INT_MAX;
    priority_queue<State, vector<State>, cmp> pq;
    dist[start] = 0;
    pq.push(State(start, 0));
    while (!pq.empty())
    {
        State state = pq.top();
        pq.pop();
        int Dist = state.weight;
        if (Dist > dist[state.id])
            continue;

        for (auto neighbor : graph[state.id])
        {
            int Dist2 = Dist + neighbor.second;
            if (dist[neighbor.first] > Dist2)
            {
                dist[neighbor.first] = Dist2;
                pq.push(State(neighbor.first, Dist2));
            }
        }
    }
}

signed main()
{
    cin >> n >> m >> s;
    int u, v, w;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        if (graph[u].count(v))
            graph[u][v] = min(graph[u][v], w);
        else
            graph[u][v] = w;
    }
    Dijkstra(s);
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " ";
    return 0;
}